package com.lun.swordtowardoffer2.c15;

import java.util.ArrayList;
import java.util.List;

public class AllPathsSourceTarget {

	public List<List<Integer>> allPathsSourceTarget(int[][] graph){
		List<List<Integer>> result = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		path.add(0);
		dfs(0, graph, result, path);
		return result;
	}

	private void dfs(int i, int[][] graph, List<List<Integer>> result, List<Integer> path) {
		if(i == graph.length - 1) {
			result.add(new ArrayList<>(path));
		}
		
		for(int index : graph[i]) {
			path.add(index);
			dfs(index, graph, result, path);
			path.remove(path.size() - 1);
		}
		
	}
	
}
